package A一周刷爆LeetCode.A基础班.E链表;

import java.util.Stack;

/**
 * @author wei.zhao
 * @description: 判断链表是不是回文结构
 * @date 2022年01月25日 11:54
 */
public class Code04_IsPalindromeList {

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(1);
        System.out.print(isPalindrome1(head) + " | ");
        System.out.print(isPalindrome2(head) + " | ");
        System.out.println(isPalindrome3(head) + " | ");

        Node head2 = new Node(1);
        head2.next = new Node(2);
        head2.next.next = new Node(3);
        head2.next.next.next = new Node(2);
        head2.next.next.next.next = new Node(1);
        System.out.print(isPalindrome1(head2) + " | ");
        System.out.print(isPalindrome2(head2) + " | ");
        System.out.println(isPalindrome3(head2) + " | ");
        System.out.println("=========================");
    }

    //将链表全部压入栈
    public static boolean isPalindrome1(Node head) {
        boolean result = true;
        Node temp = head;
        Stack<Node> stack = new Stack<>();
        while (null != temp) {
            stack.push(temp);
            temp = temp.next;
        }
        while (head != null) {
            if (stack.pop().value != head.value) {
                return false;
            }
            head = head.next;
        }
        return result;
    }

    //快慢指针找到中间节点，将后半部分压入栈
    public static boolean isPalindrome2(Node head) {
        boolean result = true;
        Stack<Node> stack = new Stack<>();
        //快慢指针，找出中间节点
        Node slow = head;
        Node fast = head;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
            fast = fast == null ? fast : fast.next;
        }
        //将右半部分压入栈
        while (slow != null) {
            stack.push(slow);
            slow = slow.next;
        }
        while (!stack.isEmpty()) {
            if (!(stack.pop().value == head.value)) {
                return false;
            }
            head = head.next;
        }
        return result;
    }

    //快慢指针找到中间节点，反转后半部分，将后半部分与前半部分逐个比较
    public static boolean isPalindrome3(Node head) {
        boolean result = true;
        //快慢指针找出中间节点
        Node slow = head;
        Node fast = head;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
            fast = fast == null ? null : fast.next;
        }
        //反转右半部分
        Node preNode = null;
        Node curNode = slow;
        while (curNode != null) {
            Node next = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = next;
        }
        //比较右半部分与左半部分
        Node rNode = preNode;
        Node lNode = head;
        while (rNode != null) {
            if (rNode.value != lNode.value) {
                return false;
            }
            rNode = rNode.next;
            lNode = lNode.next;
        }
        //将右半部分反转回来
        Node preNode2 = null;
        while (null != preNode) {
            Node next = preNode.next;
            preNode.next = preNode2;
            preNode2 = preNode;
            preNode = next;
        }
        return result;
    }

}
